public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();

        int[] nums = new int[]{0, 0, 0, 1, 0, 0, 1, 0, 1, 2, 2, 2, 1, 0};
        s.sortColors(nums);
        for(int e: nums) {
            System.out.print(e + " ");
        }
    }

    public void sortColors(int[] nums) {
        /**
         * 颜色划分
         * 解法：
         *   三指针划分数组，为三路快排的前置知识*/
        // 1 预处理
        int n = nums.length;

        // 2 三指针
        int i = 0;
        int left = -1;
        int right = n;
        while(i < right) {
            if(nums[i] == 0) {
                swap(nums, ++left, i);
            } else {
                // -由于往后交换的都是未知数，故需要循环扫描
                // -在循环时需要保证i在有效范围内
                while(i < right && nums[i] == 2) {
                    swap(nums, --right, i);
                }
                if(nums[i] == 0) {
                    swap(nums, ++left, i);
                }
            }
            i ++;
        }
    }

    public static void swap(int[] nums, int a, int b) {
        /**
         * 交换a、b下标所在元素*/
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
